﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200713
    {
        private int k=11;
        private int n=4;
        private int[] a= {1,2,4,7};
        /// <summary>
        /// 数独问题
        /// 采用深度搜索方法解决数独问题
        /// 数独问题：给定一个数列和一个数k，能不能从数列中找出几个数使其和等于k
        /// [1,2,4,7]   k=13 => 2+4+7=13
        /// http://www.zhangxymafx.com/2020/07/13/%E6%B7%B1%E5%BA%A6%E6%90%9C%E7%B4%A2----%E6%B7%B1%E5%BA%A6%E6%90%9C%E7%B4%A2%E8%A7%A3%E5%86%B3%E6%95%B0%E7%8B%AC%E9%97%AE%E9%A2%98/
        /// </summary>
        /// <returns></returns>
        public bool SolutionSudokuProblemByDfs(int i,int sum)
        {
            if (i == n-1)
                return sum+a[i] == k;

            //剪枝
            if (sum > k)
                return false;

            //当前数加，进入下一个数(走左边分支)
            if (SolutionSudokuProblemByDfs(i + 1, sum+a[i]))
                return true;
            
            //当前数不加，进入下一个数（走右边分支）
            if (SolutionSudokuProblemByDfs(i + 1, sum))
                return true;

            return false;
        }
    }
}
